package com.moyoutian.leetcode;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 * <p>
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * <p>
 * 实现词典类 WordDictionary ：
 * <p>
 * <p>
 * WordDictionary() 初始化词典对象
 * <p>
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * <p>
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 * <p>
 * <p>
 * 示例：
 * <p>
 * <p>
 * 输入：
 * <p>
 * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 * <p>
 * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 * <p>
 * 输出：
 * <p>
 * [null,null,null,null,false,true,true,true]
 * <p>
 * <p>
 * 解释：
 * <p>
 * WordDictionary wordDictionary = new WordDictionary();
 * <p>
 * wordDictionary.addWord("bad");
 * <p>
 * wordDictionary.addWord("dad");
 * <p>
 * wordDictionary.addWord("mad");
 * <p>
 * wordDictionary.search("pad"); // return False
 * <p>
 * wordDictionary.search("bad"); // return True
 * <p>
 * wordDictionary.search(".ad"); // return True
 * <p>
 * wordDictionary.search("b.."); // return True
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 1 <= word.length <= 500
 * <p>
 * addWord 中的 word 由小写英文字母组成
 * <p>
 * search 中的 word 由 '.' 或小写英文字母组成
 * <p>
 * 最多调用 50000 次 addWord 和 search
 * <p>
 * 通过次数41,649提交次数83,008
 */
public class Demo211 {
    public static void main(String[] args) {
        // a  []
        System.out.println();
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("a");
        wordDictionary.addWord("aa");
        System.out.println(wordDictionary.search("a"));
        System.out.println("Demo211.main");
    }

    public static class WordDictionary {
        Node head = new Node();

        private static class Node {
            //是否是结尾
            public boolean status;
            public Node[] nextNode;
        }

        public WordDictionary() {
        }

        public void addWord(String word) {
            Node temp = head;
            for (int i = 0; i < word.length(); i++) {
                int in = word.charAt(i) - 'a';
                if (temp.nextNode == null) {
                    temp.nextNode = new Node[26];
                }
                if (temp.nextNode[in] == null) {
                    temp.nextNode[in] = new Node();
                }
                temp = temp.nextNode[in];
            }
            temp.status = true;
        }

        public boolean search(String word) {
            if (word == null) {
                return true;
            }
            return searchDFS(word, -1, head);
        }


        public boolean searchDFS(String word, int index, Node node) {
            if (node == null) {
                return false;
            } else if (index > word.length() - 1) {
                return false;
            } else if (index == word.length() - 1) {
                return node.status;
            } else {
                index++;
                char c = word.charAt(index);
                if (c == '.') {
                    boolean flag = false;
                    for (int i = 0; i < 26; i++) {
                        flag = (node.nextNode != null && searchDFS(word, index, node.nextNode[i]) || flag);
                    }
                    return flag;
                } else {
                    return node.nextNode != null && searchDFS(word, index, node.nextNode[c - 'a']);
                }

            }
        }

    }
}
